/**
 * What is the length of the shortest pipe, of internal radius 50mm,
 * that can fully contain 21 balls of radii 30mm, 31mm, ..., 50mm?
 *
 * Give your answer in micrometres (10-6 m) rounded to the nearest integer.
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include "euler.h"

BEGIN_PROBLEM(222, solve_problem_222)
	PROBLEM_TITLE("Find the perimeter with the most right angle triangles")
	PROBLEM_ANSWER("1590933")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(3)
	PROBLEM_TIME_COMPLEXITY("N")
	PROBLEM_SPACE_COMPLEXITY("N")
END_PROBLEM()

template <typename FwdIt>
double get_pipe_length(double R, FwdIt begin, FwdIt end)
{
	if (begin == end)
		return 0;

	double last = *begin++;
	double L = last;
	while (begin != end)
	{
		double r = *begin++;
		L += std::sqrt(4.0*R*(last+r-R));
		last = r;
	}
	L += last;
	return L;
}

static void search_min_length(int R, int minr, int maxr)
{
	int nballs = maxr - minr + 1;

	std::vector<int> r(nballs);
	for (int i = 0; i < nballs; i++)
		r[i] = minr + i;

	int full = 2*std::accumulate(r.begin(), r.end(), 0);
	double best_L = full;
	std::vector<int> best_r = r;

	do 
	{
		double L = get_pipe_length(R, r.cbegin(), r.cend());
		if (L < best_L)
		{
			best_L = L;
			best_r.assign(r.begin(), r.end());
		}
	}
	while (std::next_permutation(r.begin(), r.end()));

	int sum = 2*std::accumulate(r.begin(), r.end(), 0);
	std::cout << "N=" << nballs << ", L=" << best_L << ", Saving=" << (sum-best_L) << ", Sequence:";
	std::for_each(best_r.cbegin(), best_r.cend(), [](int x) { std::cout << " " << x; });
	std::cout << std::endl;
}

static double get_max_length(int R, int nballs)
{
	// By trying a few small-scale cases, we find a pattern in the arrangement:
	// N=1, L=100, Saving=0, Sequence: 50
	// N=2, L=197.995, Saving=0.00505063, Sequence: 49 50
	// N=3, L=293.975, Saving=0.0254609, Sequence: 48 50 49
	// N=4, L=387.902, Saving=0.0978563, Sequence: 47 50 49 48
	// N=5, L=479.766, Saving=0.233552, Sequence: 47 49 48 50 46
	// N=6, L=569.512, Saving=0.487816, Sequence: 45 50 47 48 49 46
	// N=7, L=657.127, Saving=0.873464, Sequence: 44 50 46 48 47 49 45
	// N=8, L=742.55, Saving=1.45027, Sequence: 43 50 45 48 47 46 49 44
	// N=9, L=825.767, Saving=2.23281, Sequence: 42 50 44 48 46 47 45 49 43
	// N=10, L=906.714, Saving=3.286, Sequence: 41 50 43 48 45 46 47 44 49 42

	std::vector<int> r(nballs);
	int r1 = R - nballs + 1, r2 = R;
	int i1 = 0, i2 = nballs - 1;
	while (true)
	{
		r[i1++] = r1++;
		if (r1 > r2) break;
		r[i2--] = r1++;
		if (r1 > r2) break;
		r[i1++] = r2--;
		if (r1 > r2) break;
		r[i2--] = r2--;
		if (r1 > r2) break;
	}
	std::for_each(r.cbegin(), r.cend(), [](int x) { std::cout << x << " "; });
	std::cout << std::endl;
	return get_pipe_length(R, r.cbegin(), r.cend());
}

static double get_min_length(int R, int nballs)
{
	// By trying a few small-scale cases, we find a pattern in the arrangement:
	// N=1, L=100, Saving=0, Sequence: 50
	// N=2, L=197.995, Saving=0.00505063, Sequence: 49 50
	// N=3, L=293.933, Saving=0.0668131, Sequence: 49 48 50
	// N=4, L=387.765, Saving=0.23545, Sequence: 49 47 48 50
	// N=5, L=479.441, Saving=0.55928, Sequence: 49 47 46 48 50
	// N=6, L=568.91, Saving=1.0901, Sequence: 49 47 45 46 48 50
	// N=7, L=656.116, Saving=1.88362, Sequence: 49 47 45 44 46 48 50
	// N=8, L=741, Saving=3, Sequence: 49 47 45 43 44 46 48 50
	// N=9, L=823.496, Saving=4.50444, Sequence: 49 47 45 43 42 44 46 48 50
	// N=10, L=903.532, Saving=6.46794, Sequence: 49 47 45 43 41 42 44 46 48 50

	std::vector<int> r(nballs);
	int r1 = R - nballs + 1, r2 = R;
	int i1 = 0, i2 = nballs - 1;
	while (true)
	{
		r[i1++] = r2--;
		if (r1 > r2) break;
		r[i2--] = r2--;
		if (r1 > r2) break;
	}
	// std::for_each(r.cbegin(), r.cend(), [](int x) { std::cout << x << " "; });
	// std::cout << std::endl;
	return get_pipe_length(R, r.cbegin(), r.cend());
}

static void solve_problem_222()
{
#if 0
	int R = 50;
	for (int nballs = 1; nballs <= 10; nballs++)
	{
		search_min_length(R, R - nballs + 1, R);
		std::cout << "Check: " << get_min_length(R, nballs) << std::endl;
	}
#else
	double L = get_min_length(50, 21);
	std::cout << (int)(1000.0*L+0.5) << std::endl;
#endif
}
